#region File Header
//
// FiniteQueue2N.cs - A generic finite queue (ring/circular buffer) with index [] operator. 
//
// Copyright (C) Javier Valcarce. BSD License
#endregion

// Uncomment this line to check parameters in each invocation of Enqueue() or Dequeue() operations
// and to raises exceptions accordingly. If commented, checks are substituted by Debug.Assert(...) 
// which disapear in the Release version of the assembly.
#define CHECK_QUEUE

#region Using Statements
using System;
using System.Diagnostics;
using System.Collections;
using System.Collections.Generic;
#endregion

namespace Arq
{
        /// <summary>
        /// This class implements a generic finite queue (circular/bounded buffer) with index [] 
        /// operator. The capacity is always a power of two so the [] operator is very fast (bit 
        /// mask instead of modulus % operator). 
        /// 
        /// This type is designed for performance and, therefore, it does not performs checks nor 
        /// raises exceptions. Define CHECK_QUEUE symbol to override this behaviour. 
        /// Of course, it is not thread-safe.
        /// </summary>
    public class FiniteQueue2N<T> : IFiniteQueue<T>
        {
            #region Private Members
            int head;
            int tail;
            int mask;
            T[] buff;
            int count;
            int space;
            #endregion

            #region Constructor
            /// <summary>
            /// Creates a ring buffer of 2^{n} elements of type T. The performance of this data 
            /// type is high because the capacity is always power of two.
            /// </summary>
            /// <param name="n">Exponent n in 2^{n}. Must be between 1 and 22</param>
            public FiniteQueue2N(int n)
            {
                Debug.Assert(n > 00); // min  2 B buffer (in case of T=byte)
                Debug.Assert(n < 25); // max 16MB buffer (in case of T=byte)
                
                mask = 1;
                for (int i = 1; i < n; i++)
                {
                    mask |= (1 << i);
                }
                
                buff = new T[(1 << n)];
                Clear();
                
            }

            /// <summary>
            /// Creates a ring buffer using a T array as the underlaying storage. The length of
            /// this array must be a power of two between 2^{1} and 2^{22}.
            /// </summary>
            /// <param name="v">Array of T elements</param>
            public FiniteQueue2N(T[] v)
            {
                Debug.Assert(v.Length > 0);
                Debug.Assert(IsPowerOfTwo((ulong)v.Length));

                mask = 1;
                for (int i = 1; i < v.Length; i++)
                {
                    mask |= (1 << i);
                }

                buff = v;
                Clear();
            }

            bool IsPowerOfTwo(ulong x)
            {
                // warning: zero is detected as power of two
                return (x & (x - 1)) == 0;
            }

            #endregion

            #region Public Methods
            /// <summary>
            /// Removes all objects from the RingBuffer<![CDATA[<T>]]>
            /// </summary>
            public void Clear()
            {
                head  = 0;
                tail  = 0;
                count = 0;
                space = buff.Length;
            }

            /// <summary>
            /// Enqueue a single object to the end of the RingBuffer<![CDATA[<T>]]>
            /// </summary>
            /// <param name="item"></param>
            public int Enqueue(T item)
            {
#if CHECK_QUEUE
                if (space < 1)
                    throw new InvalidOperationException();
#else
                Debug.Assert(!(space < 1));
#endif

                buff[tail] = item;
                // fast modulus operation
                tail = (tail + 1) & mask; 
                
                count++;
                space--;
                return 1;
            }

            /// <summary>
            /// Enqueue an array of objects to the end of the RingBuffer<![CDATA[<T>]]>
            /// </summary>
            /// <param name="item"></param>
            public int Enqueue(T[] src, int offset, int count)
            {
#if CHECK_QUEUE
                if (count > space)
                    throw new InvalidOperationException();
                if (count < 1)
                    throw new ArgumentException();
#else
                Debug.Assert(!(count > space));
                Debug.Assert(!(count < 1));
#endif

                for (int i = 0; i < count; i++)
                {
                    buff[tail] = src[offset + i];
                    // fast modulus operation
                    tail = (tail + 1) & mask; 
                }

                this.count += count;
                this.space -= count;
                return count;
            }

            /// <summary>
            /// Removes and returns the object at the beginning of the RingBuffer<![CDATA[<T>]]> 
            /// </summary>
            /// <returns></returns>
            public int Dequeue(out T item)
            {
#if CHECK_QUEUE
                if (this.count < 1)
                    throw new InvalidOperationException();
#else
                Debug.Assert(!(this.count < 1));
#endif                
                item = buff[head];
                head = (head + 1) & mask; // fast modulus operation
                this.count--;
                this.space++;
                return 1;
            }

            public int Dequeue(T[] dst, int offset, int count)
            {
#if CHECK_QUEUE
                if (count > this.count)
                    throw new InvalidOperationException();
                if (count < 1)
                    throw new ArgumentException();
#else
                Debug.Assert(!(count > this.count));
                Debug.Assert(!(count < 1));
#endif
                for (int i = 0; i < count; i++)
                {
                    dst[offset + i] = buff[head];
                    head = (head + 1) & mask; // fast modulus operation
                }
               
                this.count -= count;
                this.space += count;
                return count;
            }
            #endregion

            #region Properties
            /// <summary>
            /// Index operator
            /// </summary>
            /// <param name="index">Zero-based index. Index 0 is the head of the queue. No Bound 
            /// Check Is Performed</param>
            /// <returns>The indexed element</returns>
            public T this[int index]
            {
                get 
                {
#if CHECK_QUEUE
                    if (index >= this.count)
                        throw new InvalidOperationException();
                    if (index < 0)
                        throw new ArgumentException();
#else
                    Debug.Assert(!(index >= this.count));
                    Debug.Assert(!(index < 0));
#endif           
                    return buff[(head + index) & mask]; 
                } 

                set 
                {
#if CHECK_QUEUE
                    if (index >= this.count)
                        throw new InvalidOperationException();
                    if (index < 0)
                        throw new ArgumentException();
#else
                    Debug.Assert(!(index >= this.count));
                    Debug.Assert(!(index < 0));
#endif
                    buff[(head + index) & mask] = value; 
                } 
            }

            /// <summary>
            /// Queues's capacity
            /// </summary>
            public int Capacity
            {
                get
                {
                    return buff.Length;
                }
            }
            
            /// <summary>
            /// Number of elements in the queue
            /// </summary>
            public int Count
            {
                get
                {
                    return count;
                }
            }

            /// <summary>
            /// Available free space in the queue
            /// </summary>
            public int Space
            {
                get
                {
                    return space;
                }
            }            
            #endregion

        }
}
